package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code79JumpGame2 {

    public int jump(int[] nums) {
        int rightMost = 0;
        int right = 0;
        int steps = 0;
        // 最后一格不需要跳
        for (int i = 0; i < nums.length - 1; i++) {
            rightMost = Math.max(rightMost, i + nums[i]);
            // 每步都尝试跳到最远
            // 如果当前位置刚好到达最大可跳跃位置, 更新下一步最大可跳跃位置
            if (i == right) {
                right = rightMost;
                steps++;
            }
        }
        return steps;
    }
}
